//Mon Jun  6 15:02:54 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int dx[] = {1, 1, 0, -1, -1, -1, 0, 1, 2, 1, -1, -2, -2, -1, 1, 2};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1, 1, 2, 2, 1, -1, -2, -2, -1};

class ChessMetric {
public:
	long long howMany(int, vector <int>, vector <int>, int);
	long long dfs(int, int, int, int, int);
	bool checkBound(int x, int y);
	long long grid[101][101][51];
	int size;
};

long long ChessMetric::howMany(int sz, vector <int> start, vector <int> end, int numMoves) {
	size = sz;
	memset(grid, -1, sizeof(grid));
	return dfs(start[0], start[1], end[0], end[1], numMoves);
}

long long ChessMetric::dfs(int cx, int cy, int ex, int ey, int moves){
	if(moves ==0) return cx==ex && cy==ey;
	long long &ret = grid[cx][cy][moves];
	if(ret != -1) return ret;
	ret = 0;
	for(int i=0; i<16; i++){
		int xx = cx + dx[i];
		int yy = cy + dy[i];
		if(checkBound(xx, yy)){
			ret += dfs(xx, yy, ex, ey, moves-1);
		}
	}
	return ret;
}

bool ChessMetric::checkBound(int x, int y){
	return x>=0 && x<size && y>=0 && y<size;
}

<%:testing-code%>
//Powered by [KawigiEdit] 2.0!
